/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/implement-trie-prefix-tree
   @Language: C++
   @Datetime: 20-01-07 14:31
   */

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

class Trie {
	static const int SIZE = 26;
	Trie *children[SIZE];
	bool isString;
public:
	/** Initialize your data structure here. */
	Trie() {
		for(int i=0; i<SIZE; children[i++]=NULL);
		isString = false;
	}
	~Trie(){
		for(int i=0; i<SIZE; ++i)
			if(children[i]) delete children[i];
	}

	/** Inserts a word into the trie. */
	void insert(string word) {
		Trie *node = this;
		for(const auto &ch:word){
			if (node->children[ch-'a']==NULL)
				node->children[ch-'a'] = new Trie();
			node = node->children[ch-'a'];
		}
		node->isString = true;
	}

	/** Returns if the word is in the trie. */
	bool search(string word) {
		Trie *node = this;
		for(const auto &ch:word){
			if(node==NULL) return false;
			node = node->children[ch-'a'];
		}
		return node && node->isString;
	}

	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
		Trie *node = this;
		for(const auto &ch:prefix){
			if(node==NULL) return false;
			node = node->children[ch-'a'];
		}
		return node;
	}
};


